Many conventional search engine systems typically include one or more search engine devices. A search engine device can include circuitry for performing one or more types of search operations. In a search operation, a comparand (or key) may be compared to multiple entries to see if all or a portion of the key matches an entry. After a search operation, a search engine may give a search result as an output. Typically a search result may include an “index” value, which may be used to access associated data to provide data itself.
Search engine devices may take a variety of forms. As but a few of the possible examples, some search engine devices are based on particular types of content addressable memory (CAM) cells. Such CAM cells may include storage circuits integrated with compare circuits. Examples of storage circuits may be static random access memory (SRAM) type cells or dynamic random access memory (DRAM) type cells. Alternate approaches to search engines may include random access memories (RAM) arrays, or the like, with separate matching circuits and/or processes.
Referring now to FIG. 19, a conventional CAM device 1900 will be described in more detail. A CAM device 1900 may include a CAM array 1902, CAM control circuits 1904, and comparand registers (CMPR) 1906.
A CAM array 1902 may have a number of entries for storing data values for comparison with a key value. Each entry may include a number of CAM cells. Data may be written to and/or read from entries. In particular embodiments, a key may be compared against multiple data values stored in such entries. If a data value in a CAM entry matches a key, a search hit may be indicated. Otherwise a search miss may be indicated. Search hits may generate index values. Entries within a CAM array 1902 can be divided into groups. As but one example, entries may be grouped into “blocks” that may have one or more common features (e.g., address range, or other programmable values). Still further, blocks may be divided into “sub-blocks” that may also have common features.
A CAM control circuit 1904 can take CAM control signals as inputs and generate signals that may control the operation of a CAM array 1902 and/or comparand registers CMPR 1906. Comparand registers CMPR 1906 can include a number of storage locations that may store key values used for search and other operations.
Having described an example of a CAM device, a conventional CAM search operation will now be described. To perform a search operation, a device such as a network processing unit (NPU) may provide a search command to a CAM device 1900 on a data/control bus 1908. Such a command may include a key value that can be compared to all or a portion of CAM entries within a CAM array 1902. A key value may then be stored in comparand registers CMPR 1906.
A CAM array 1902 may generate a result according to a comparison between a key and entries. Results may take various forms, including match results and/or miss results. If a key matches only one CAM entry, a single match result may be generated. If a key matches more than one CAM entry, a multiple match result may be generated. If a key does not match any entries, a miss result may be generated. Results may be provided on a result bus 1910. A single match result may take various forms. Typically, a single match result may be an index value that points to associated data, or the actual associated data itself. Multiple match and/or miss results may be indicated by particular output flags or the like.
One current application for search engine systems can be the processing of network packets. Search engine systems based on CAM devices, sometimes also referred to as “associative memory” systems, can provide rapid matching functions that are often included in routers and network switches to process network packets. As just one example, a router can use a matching function to match the destination (e.g., a destination Internet Protocol (IP) address) of an incoming packet with a “forwarding” table entry. The forwarding table entry can provide “next hop” information that can allow the incoming packet to be transmitted to its final destination, or to another node on the way to its final destination. Of course, search engine systems can also be used for applications other than network hardware.
To better understand the various features and aspects of a search engine system and system performance, two conventional search engine systems will now be described.
A first conventional search engine system is shown in FIG. 20 and designated by the general reference character 2000. A conventional search engine system 2000 may be based on CAMs, and thus include one or more CAM devices, each of which may perform a search operation. In the example of FIG. 20, a search engine system 2000 includes “n+1” CAM devices, shown as 2002-0 to 2002-n. A search engine system 2000 may perform search operations in response to commands from a requesting device. In FIG. 20, a requesting device is an NPU 2004.
FIG. 20 shows an example of a bus based search engine system. In a bus based search engine system, CAM devices may be commonly connected to a requesting device and to one another by a common bus. Thus, in FIG. 20 CAM devices (2002-0 to 2002-n) can be commonly connected to each other and to an NPU 2004 by a bus 2006.
A drawback to bus based systems can be speed limitations. Larger interconnect lengths of bus lines as well as the input capacitances of each device can present considerable capactive loads for an NPU 2004 and CAM devices (2002-0 to 2002-n). Thus, while a bus based search engine system 2000 may be scaled up by increasing the number of CAM devices (2002-0 to 2002-n), such an approach may increase bus loading, reducing performance.
A bus based search engine system 2000 may have other drawbacks. Some sort of bus or other arbitration may be necessary to select one of multiple possible results. That is, while a search request may be issued from an NPU 2004 to CAM devices (2002-0 to 2002-n) simultaneously, individual search results for the CAM devices (2002-0 to 2002-n) can be generated, and some sort of mechanism may have to be included to select which particular response would be received separately by an NPU 2004. Special bus arbitration hardware may allow a “winning” device to transmit a result to an NPU 1604.
Further, some additional processing may be needed to process multiple results from multiple CAM devices. As but one example, more than one CAM device (2002-0 to 2002-n) may generate a match result in response to a key. Some sort of evaluation would then be necessary to establish a precedence between CAM devices (2002-0 to 2002-n). It is noted that such a precedence may make a system inflexible. As more and more CAM devices (2002-0 to 2002-n) are added, evaluating a search result can require that precedence between all devices must be know to ensure a highest precedence device result is provided as an output.
In particular bus based search engine systems, each CAM device may simultaneously compare a key with entries of its respective CAM array. If a CAM device has a match, the CAM device may forwards a match indication (e.g., a flag or the like) to a next, lower priority CAM device. A higher priority CAM device may output a result and a lower priority CAM device can be disabled from outputting data to the common output bus. If, however, a higher priority CAM device does not have a match, such a device may not assert a match indication, and a lower priority CAM device can provide an output result.
Such an approach may have the drawbacks of more complex connections, limited flexibility, and increased processing rate (rate at which results may be generated). More complex connections may arise, as a match indication must be transmitted from a higher priority CAM device to a lower priority CAM device. Such connections are not part of a bus, as such signals cannot be shared. Limited flexibility arises in that CAM device priority can be established by CAM device order. Thus, scaling such a system higher can require a design change to support additional circuits.
Increased processing rates may occur when many CAM devices are cascaded together. In such an arrangement, a lowest priority CAM device in the cascade may only output a result to a common output bus if no other previous higher priority CAM devices in the cascade have a match. That is, a lowest priority CAM device must wait until match indications from all previous CAM devices have rippled through each CAM device in a system. This may result in undesirably slow processing rates.
One way to increase a processing rate for systems like that described above, can be for each CAM device to provide a match indication to all lower priority CAM devices. Such a configuration can undesirably increase the number of input/output (I/O) pins and connections. Still further, in a “worst” case match (a match in a lowest priority CAM device), a match result cannot be generated until all higher priority devices generate a result.
A second conventional CAM system is set forth in FIG. 21 and designated by the general reference character 2100. A second conventional CAM system 2100 may include a number of CAM devices (2102-0 to 2102-3) having common connections to a command and data bus 2104, as well as separate common connections to an index or result bus 2106. Optionally, an index or result bus 2106 may be connected to one or more memory devices 2108, such as a static random access memory (SRAM).
In a system like that shown in FIG. 21, a search command may be issued from a host device 2110 on a command and data bus 2104. CAM devices (2102-0 to 2102-3) may process such commands and generate results, which may be output on an index or result bus 2106. Results may be returned to a command issuing host device 2110 by way of a result bus. Optionally, results may be applied to one or more memory devices 2108 to generate data that may then be accessed by a host device 2110.
A second conventional system 2100 may suffer from many of the drawbacks noted above. If a number of CAM devices is increased, bus loading can grow correspondingly. Further, some sort of logical protocol may be necessary to establish priority between results of multiple CAMs. As the number of CAM devices grows, such a protocol may get more complex or involve greater time periods for execution.
In light of the above, it would be desirable to arrive at some cascaded CAM system that may generate responses at an overall faster rate than conventional approaches, like that described above.